package com.wk.arth;

import com.wk.common.Node;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.Stack;

/**
 * 迷宫 最短距离
 * bfs算法
 * @author wukai
 * @date 2023/5/26 18:03
 */
public class Maze {
    private class Pointer{
        private int x;
        private int y;
        public Pointer(int x,int y){
            this.x = x;
            this.y = y;
        }
    }
    // 迷宫数组
    int[][] map;
    // 起点
    int startX;
    int startY;
    // 终点
    int endX;
    int endY;
    // 4个方向
//    int[] dx = {0,0,-1,1};
//    int[] dy = {1,-1,0,0};
    private int[] dx = {1,0,-1,0};
    private int[] dy = {0,1,0,-1};

    public Maze(int[][] map,int startX,int startY,int endX,int endY){
        this.map = map;
        this.startX = startX;
        this.startY = startY;
        this.endX = endX;
        this.endY = endY;
    }
    public void print() {
        for(int i=0; i<map.length; i++) {
            for(int j=0; j<map[0].length; j++) {
                System.out.printf("%4d",map[i][j]);
            }
            System.out.println();
        }
    }
    public void bfs(){
        Deque<Pointer> queue = new ArrayDeque<>();
        // 存储每个节点的前驱节点到这一步的操作
        int[][] pre = new int[map.length][map[0].length];
        // 存储每个点的最短距离
        int[][] dis = new int[map.length][map[0].length];
        for (int[] di : dis) {
            Arrays.fill(di,100);
        }
        queue.offer(new Pointer(startX,startY));
        dis[startX][startY] = 0;
        map[startX][startY] = 2;
        while (!queue.isEmpty()){
            Pointer temp = queue.poll();
            for(int i=0;i<4;i++){
                int tx = temp.x+dx[i];
                int ty = temp.y+dy[i];
                if(map[tx][ty] == 0){
                    queue.offer(new Pointer(tx,ty));
                    dis[tx][ty] = dis[temp.x][temp.y]+1;
                    map[tx][ty] = 2;
                    pre[tx][ty] = i;
                }
            }
        }
        int a = this.endX;
        int b = this.endY;
        System.out.printf("从(%d,%d)到(%d,%d)的最短距离是：%d，路线为：\n",
                this.startX, this.startY, a, b, dis[a][b]);
        //倒序访问最短路径的路线并入栈
        Deque<Pointer> stack2 = new ArrayDeque<>();
        stack2.push(new Pointer(a, b));
        while(a != this.startX || b != this.startY) {
            int da = dx[pre[a][b]];
            int db = dy[pre[a][b]];
            a = a - da;
            b = b - db;
            stack2.push(new Pointer(a,b));
        }
        //出栈的顺序就是从起点到终点的路线
        while(!stack2.isEmpty()) {
            Pointer p = stack2.pop();
            System.out.printf("(%d,%d)->",p.x,p.y);
        }
    }
    public static void main(String[] args) {
        //创建一个迷宫并初始化
        int[][] map = new int[8][8];
        for(int i=0; i<map.length; i++) {
            for(int j=0; j<map[0].length; j++) {
                map[i][j] = 0;
            }
        }
        for(int i=0; i<map.length; i++) {
            map[i][0] = -1;
            map[i][7] = -1;
            map[0][i] = -1;
            map[7][i] = -1;
        }
        map[4][1] = -1;
        map[4][2] = -1;
        map[5][3] = -1;
        map[4][4] = -1;
        map[3][4] = -1;
        Maze maze = new Maze(map, 1, 1, 5, 5);
        maze.print();
        maze.bfs();
        maze.print();
    }
}
